package myalg.fibonacci;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Pavel Belevich
 *         Date: Jul 26, 2012
 *         Time: 11:10:12 AM
 */
public class MatrixFibonacci {

    private Map<Integer, BigInteger[][]> memo = new HashMap<Integer, BigInteger[][]>();

    BigInteger[][] q = {
            {BigInteger.valueOf(1), BigInteger.valueOf(1)},
            {BigInteger.valueOf(1), BigInteger.valueOf(0)}
    };

    BigInteger[][] i = {
            {BigInteger.valueOf(1), BigInteger.valueOf(0)},
            {BigInteger.valueOf(0), BigInteger.valueOf(1)}
    };

    BigInteger[][] multiplyMatrices(BigInteger[][] m1, BigInteger[][] m2) {
        BigInteger a00 = m1[0][0].multiply(m2[0][0]).add(m1[0][1].multiply(m2[1][0]));
        BigInteger a01 = m1[0][0].multiply(m2[0][1]).add(m1[0][1].multiply(m2[1][1]));
        BigInteger a10 = m1[1][0].multiply(m2[0][0]).add(m1[1][1].multiply(m2[1][0]));
        BigInteger a11 = m1[1][0].multiply(m2[0][1]).add(m1[1][1].multiply(m2[1][1]));
        return new BigInteger[][] {{a00, a01}, {a10, a11}};
    }

    BigInteger[][] getMatrixPower(BigInteger[][] m, int p) {
        if (p == 1)
            return m;
        if (this.memo.containsKey(p))
            return this.memo.get(p);
        BigInteger[][] k = getMatrixPower(m, p/2);
        BigInteger[][] r = multiplyMatrices(k, k);
        this.memo.put(p, r);
        return r;
    }

    BigInteger getNumber(int n) {
        if (n == 0)
            return BigInteger.ZERO;
        if (n == 1)
            return BigInteger.ONE;

        char[] bin = Integer.toBinaryString(n-1).toCharArray();
        BigInteger[][] r = i;
        for (int i = 0 ; i < bin.length  ; i++) {
            if ('1' == bin[bin.length-i-1]) {
                r = multiplyMatrices(r, getMatrixPower(q, (int) Math.pow(2, i)));
            }
        }
        return r[0][0];
    }

    public static void main(String[] args) {
        MatrixFibonacci matrixFibonacci = new MatrixFibonacci();
        for (int i = 0 ; i < 128; i++) {
            System.out.println(matrixFibonacci.getNumber(i));
        }
    }

}
